package Stack;

import java.awt.List;
import java.util.ArrayList;
import java.util.Stack;

public class PolandNotation {

	public static void main(String[] args) {
		//***************************************
		//用后缀表达式，计算（逆波兰表达式），用系统栈代替
		//(3+4)*5-6 => 后缀表达式为，34+5*6-
//		String expression = "3 4 + 5 * 6 -";
		//思路：
		//1、先将 "3 4 + 5 * 6 -"放入arrayList中，
		//2、遍历arraylist，配合栈，完成运算
//		String[] strings = expression.split(" ");
//		Stack<Integer> stack = new Stack<Integer>();
//		int i = 0;
//		String oper;
//		while(true) {
//			if(i>=strings.length) {
//				break;
//			}
//			if(strings[i].matches("\\d+")) {//是数，则入栈
//				stack.push(Integer.parseInt(strings[i]));
//			}else {//是符号
//				oper = strings[i];
//				stack.push(calculator(stack.pop(),stack.pop(),oper));	
//			}
//			i++;			
//		}
//		System.out.println("最终结果："+stack.pop());
		
		//***************************************
		//中缀表达式转后缀表达式
		//思路理解：
		/**
		 * 1、新建两个栈：操作符栈、结果栈
		 * 2、遍历公式
		 * 3、当访问到数字时，直接进结果栈
		 * 4、当访问到操作符时，做判断：
		 * 		4.1、如果操作符栈为空，直接进栈；否则：
		 * 		4.2、如果操作符为‘(’，直接进栈;
		 * 		4.3、如果为')',将操作符栈中，从栈顶到第一个‘(’的所有元素出栈，并顺序放入结果栈（先出先放原则）
		 *      4.3、如果操作符优先级比操作符栈顶元素优先级高，直接进栈；否则，将栈顶元素出栈，并放入结果栈，并再次查看此时的栈顶
		 *      元素，如果依旧高于待放入的操作符优先级，则重复如上操作，直到栈顶元素的优先级不高于待放入操作符的优先级
		 * 5、继续遍历公式，直至结束
		 * 6、让操作符栈的所有元素，顺序压入结果栈，将结果栈逆序输出，即为后缀表达式
		 * 
		 */
		String expression = "1+((2+3)*4)-5";
		ArrayList<String> list = toList(expression);
		System.out.println(list.toString());
		hou(list);
		
		
		
		
		
	}
	public static ArrayList<String> toList(String s) {
		ArrayList<String> list = new ArrayList<String>();
		int i = 0;//遍历指针
		String num = "";
		while(i<s.length()) {
			if(s.charAt(i)<48||s.charAt(i)>57) {//非数字0-9
				list.add(s.charAt(i)+"");
				i++;
			}else {
				while (i<s.length()&&s.charAt(i)>=48 && s.charAt(i)<=57) {
					num += s.charAt(i);//拼接数字，防止是两位数
					i++;			
				}
				list.add(num);
				num = "";
			}
		}
		return list;
		
	}
	
	public static void hou(ArrayList<String> list) {
		if(list.size()<1) {
			System.out.println("请输入表达式！");
			return;
		}
		Stack<String> operStack = new Stack<String>();
		Stack<String> resStack = new Stack<String>();
		String item = "";
		String item_oper = "";
		//遍历公式
		for (int i = 0; i < list.size(); i++) {
			item = list.get(i);
			//是操作符
			if(isOper(item)) {
				if(operStack.size()<1) {
					operStack.push(item);
				}else if(item.equals("(")) { //是不是括号 '('
						operStack.push(item);							
					}else if(item.equals(")")){//是不是括号 ')'
						item_oper = "";
						//如果为')',将操作符栈中，从栈顶到第一个‘(’的所有元素出栈，并顺序放入结果栈（先出先放原则）
						while(true) {
							item_oper = operStack.pop();
							if(item_oper.equals("(")) {
								break;
							}
							resStack.push(item_oper);
						}
					//如果操作符优先级比操作符栈顶元素优先级高，直接进栈；否则，将栈顶元素出栈，并放入结果栈，并再次查看此时的栈顶
					//元素，如果依旧高于待放入的操作符优先级，则重复如上操作，直到栈顶元素的优先级不高于待放入操作符的优先级
					}else {						
						while(true) {
							if(operStack.size() == 0||getPrivatory(item)>getPrivatory(operStack.peek())) {//其他操作符
								operStack.push(item);
								break;
							}
							item_oper = operStack.pop();
							resStack.push(item_oper);							
						}
					}
			//是数字
			}else {
				resStack.push(item);
			}
		}
		
		while(true) {
			if(operStack.size() == 0) {
				break;
			}
			resStack.push(operStack.pop());
		}
		System.out.println(resStack.toString());
	}
	
	
	public static boolean isOper(String s) {
		return s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")");
	}
	public static  int getPrivatory( String oper) {
		int privatory = 0;
		if(oper.equals("+")||oper.equals("-")) {
			privatory = 1;
		}
		if(oper.equals("*")||oper.equals("/")) {
			privatory = 2;
		}
		return privatory;
	}
	
	

	private static Integer calculator(int pop1, int pop2, String oper) {
		// TODO Auto-generated method stub
		int res = 0;
		switch (oper) {
		case "+":
			res = pop2 + pop1;
			break;
		case "-":
			res = pop2 - pop1;
			break;
		case "*":
			res = pop2 * pop1;
			break;
		case "/":
			res = pop2 / pop1;
			break;
		default:
			throw new RuntimeException("运算符错误，请检查！");
		}
		return res;
	}

}
